1. Field of Use
The present invention relates to data processing and more particularly to state machine apparatus.
2. Prior Art
It is well known to use ROM or PROM controlled state machines to produce control signals from previous state and instruction inputs. Such state machines normally comprise a set of state flip-flops whose state is switched as a function of input status signals generated during a previous cycle of operation. Examples of such state machines are disclosed in U.S. Pat. Nos. 4,875,160 and 4,835,733 which issued on Oct. 17, 1989 and May 30, 1989, respectively.
The introduction of field programmable ROM's (PROM's) simplified the process of realizing synchronous sequential circuits by enabling the development of stored state techniques. In such an arrangement, the PROM contains the state table and generates from the current state and inputs, a next state and outputs which are inputs to a register. State changes occur periodically and synchronously with the system clock. This type of arrangement is discussed in the article entitled, "Stored State Asynchronous Sequential Circuits," by Alan B. Hayes, published in IEEE Transactions on Computers, Vol. C-30, No. 8, August 1981, pages 596-600. However, when it becomes necessary to increase the number of inputs to the state machine and number of states, circuit complexity of conventionally realized asynchronous state machines increase very rapidly. Thus, one approach has been to decompose a single machine/unit design into a collection of smaller and more easily realizable state machines. This approach typically is found to increase the part count and substantially slow down the operation of the unit.
In the case of VLSI circuits, it has been a common practice to implement smaller finite state machines (FSM's) as single programmable logic array (PLA) FSM's with delay (D) latches used as state memories. When large FSM's are implemented, more comprehensive structures are required. In such cases, the next state function and the output functions are implemented in several PLA's. Additionally, the state memory is implemented by a loadable counter. This approach is used as the control structure for various microprocessor designs and is discussed in the article entitled, "Optimal State Chains and State Codes in Finite State Machines," by Rainer Amann and Utz G. Baitinger, published in IEEE Transactions on Computer-Aided Design, Vol. 8, No. 2, February 1989, pages 153-170.
The above approach still lacks the requisite flexibility in assigning states which can take into account any time dependencies or hardware requirement of other units which operate in conjunction with the state machine unit. For example, when the unit is a virtual memory unit (VMU), it is required to perform the function of translating virtual addresses into physical addresses. If the VMU is included as one stage of a pipelined machine, any delay in performing the translation can seriously impact the overall performance of the machine. The process of performing such translations is complicated where the VMU is required to provide support for other pipeline stages, particularly where certain time dependencies and hardware requirements exist.
Accordingly, it is a primary object of the present invention to provide state machine apparatus and method which is highly programmable.
It is a further object of the present invention to provide a programmable state machine which can be readily altered to accommodate unforeseen time dependencies and additional hardware requirements.